/**
 *  filename:   consecutive_seq.c
 *  author:     大梦
 *  date:       2015/4/11
 *  desc:       2.1.6 Longest Consecutive Sequence
 *  history:
 *              2015/4/11 create the file
 */

#include <stdio.h>
#include <unordered_map>
#include <vector>

using namespace std;

int consecutive_seq(const vector<int> &num)
{
    unordered_map<int, bool> used;
    for (auto i : num) used[i] = false;

    int longest = 0;
    for (auto i : num)
    {
        if (used[i]) continue;
        int length = 1;
        used[i] = true;
        for (int j = i + 1; used.find(j) != used.end(); ++j)
        {
            used[j] = true;
            ++length;
        }
        for (int j = i - 1; used.find(j) != used.end(); --j)
        {
            used[j] = true;
            ++length;
        }
        longest = max(longest, length);
    }
    return longest;
}

int main ()
{
    vector <int>vi;
    vi.push_back(100);
    vi.push_back(2);
    vi.push_back(3);
    vi.push_back(1);
    vi.push_back(4);
    vi.push_back(101);
    vi.push_back(6);
    /* vi.push_back(5); */

    int rtn = consecutive_seq(vi);

    printf("longest consecutive seq: %d\n", rtn);

    return 0;
}


#if 0
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1,
        2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
#endif // 0
